package top.carrotguo.bean.linklist;

/**
 * @Author: Carrot
 * @Mail: 1053155183carrot@gmail.com
 * @Date: Created in 23:12 2018-05-29
 */
public class IntLinkList extends LinkList<Integer>{
    /**
     * 有序链表唯一化
     * @return
     */
    public int uniquify(){
        if (size < 2) {
            return 0;
        }
        int oldSize = size;
        //定义指向第一个结点的p
        LinkNode<Integer> p = head.nextNode;
        //定义指向p后继结点的q
        LinkNode<Integer> q;
        while (tail!=(q=p.nextNode)) {
            if (p.value != q.value) {
                p = q;
            } else {
                remove(q);
            }
        }
        return oldSize - size;
    }


    /**
     * 在p的n个前驱中查找不大于e的结点(仅限int数值元素)
     * @param e 查找元素
     * @param n n个前驱
     * @param p 从p的前驱开始查找
     * @return
     */
    public LinkNode<Integer> search(int e, int n, LinkNode<Integer> p){
        while (0<n--) {
            if ((p=p.preNode).value <= e)
                break;
        }
        return p;
    }

    /**
     * linkNode的n个后继中查找最大结点并且返回
     * @param p 查找开始位置
     * @param n 查找的个数范围
     * @return
     */
    public LinkNode<Integer> searchMax(LinkNode<Integer> p, int n){
        LinkNode<Integer> maxNode = p;
        while (0<n--) {
            if (maxNode.value<p.value) {
                maxNode = p;
            }
            p = p.nextNode;
        }
        return maxNode;
    }

    /**
     * 选择排序（选择最大的放到尾部）
     * @param p 排序开始位置
     * @param n 排序的元素个数
     */
    public void selectionSort(LinkNode<Integer> p, int n){
        //待排序区间(head,tail)
        LinkNode head = p.preNode;
        LinkNode tail = p;
        //tail指向链表尾
        for (int i=0; i<n; i++) {
            tail = tail.nextNode;
        }
        while (1<n) {
            insertBefore(remove(searchMax(head.nextNode,n)),tail);
            //尾部向前移动一位  因为最后一位已经是筛选出来最大的
            tail = tail.preNode;
            n--;
        }
    }

}
